package com.demo.java.OD301_350.OD336;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【恢复数字序列(B卷)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146154344
 */
public class OdMain {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取输入的字符串和整数k，使用空格分隔并存储在data数组中
        String[] data = scanner.nextLine().split(" ");
        String s = data[0]; // 输入的字符串
        int k = Integer.parseInt(data[1]); // 整数k

        // 调用solveMethod函数，计算并输出结果
        int result = solveMethod(s, k);
        if (result != -1) {
            System.out.println(result);
        }
    }

    // 定义函数solveMethod，用于解决问题
    public static int solveMethod(String s, int k) {
        // 创建原始字符串的字符统计映射originMap
        Map<Character, Integer> originMap = new HashMap<>();
        for (char c : s.toCharArray()) {
            originMap.put(c, originMap.getOrDefault(c, 0) + 1);
        }

        // 创建大小为k的滑动窗口字符统计映射windowMap
        Map<Character, Integer> windowMap = new HashMap<>();
        for (int i = 1; i <= k; i++) {
            // 将窗口中的字符统计更新为1，用数字字符串表示窗口内字符
            updateCharMap(Integer.toString(i), windowMap, true);
        }

        // 比较原始字符串的字符统计映射originMap和滑动窗口字符统计映射windowMap
        if (compareCharMaps(originMap, windowMap)) {
            // 如果两个映射相等，则返回1（表示第一个窗口即为所求）
            return 1;
        } else {
            // 否则，从第二个窗口开始，通过滑动窗口更新字符统计映射，并继续比较
            for (int i = 2; i <= 1000 - k + 1; i++) {
                // 移动滑动窗口，去掉第一个字符，加上下一个字符
                updateCharMap(Integer.toString(i - 1), windowMap, false);
                updateCharMap(Integer.toString(i + k - 1), windowMap, true);

                // 比较原始字符串的字符统计映射originMap和滑动窗口字符统计映射windowMap
                if (compareCharMaps(originMap, windowMap)) {
                    // 如果两个映射相等，则返回当前窗口的起始位置i
                    return i;
                }
            }
        }

        // 如果没有找到满足条件的窗口，则返回-1
        return -1;
    }

    // 定义函数compareCharMaps，用于比较两个字符统计映射是否相等
    private static boolean compareCharMaps(Map<Character, Integer> map1, Map<Character, Integer> map2) {
        for (char c : map1.keySet()) {
            if (!map2.containsKey(c) || !map1.get(c).equals(map2.get(c))) {
                // 如果两个映射不相等，则返回false
                return false;
            }
        }
        // 如果两个映射相等，则返回true
        return true;
    }

    // 定义函数updateCharMap，用于更新字符统计映射
    private static void updateCharMap(String num, Map<Character, Integer> charMap, boolean isAdd) {
        for (char c : num.toCharArray()) {
            // 如果isAdd为true，则增加字符c的计数；否则减少字符c的计数
            charMap.put(c, charMap.getOrDefault(c, 0) + (isAdd ? 1 : -1));
        }
    }
}